package 查找算法;
/*
* 插值查找
* 适用于数据分布均匀,数据量大的集合
* int mid = left + (right+left)*(fidVal-arr[left])/(arr[right] - arr[left])
* */
public class InterpolationSearch {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
        int index = insertValueSearch(arr,0,arr.length-1,1);
        if(index == -1){
            System.out.println("找不到");
        }else{
            System.out.println("找到了,索引为"+index);
        }
    }
    public static int insertValueSearch(int[] arr, int left, int right, int fidVal){
        // fidVal < arr[left] || fidVal > arr[right] 必须有,否则mid可能会越界
        if(left > right || fidVal < arr[left] || fidVal > arr[right]){
            return -1;
        }
        // 自适应
        int mid = left + (right+left)*(fidVal-arr[left])/(arr[right] - arr[left]);
        int midVal = arr[mid];
        if(fidVal < midVal){// 向左递归
            return insertValueSearch(arr,left,mid-1,fidVal);
        }else if(fidVal > midVal){// 向右递归
            return insertValueSearch(arr,mid+1,right,fidVal);
        }else{
            return mid;
        }
    }
}
